package day26;

// 青蛙跳台阶问题：【递归经典题型】--Fibonacci
// 一次1 or 2 or ...n 台阶，求跳法数
// 在稿纸上自己试试找规律：0 1 2 4 8 15 31...
// 发现规律：该台阶的跳法= 前面所有台阶的跳法之和
// 即： fib(n) = fib(n-1)+fib(n-2)+fib(n-3) +...+fib(1)+fib(0)-->也就是递归
// fib(n-1) = fib(n-2)+fib(n-3) +...+fib(1)+fib(0)
// 所以说： fib(n) = 2*fib(n-1) !!!! =>推导出来！

public class Main1 {
    public int jumpFloorII (int number) {
        // 使用递归
        if(number < 3) {
            return number;
        }
        // 来到这儿，说明 num>=3
        // 使用 fib(n) = 2*fib(n-1)  //也就是递归
        return 2 * jumpFloorII(number-1);
    }


    public static void main(String[] args) {

    }
}
